A receiver is broadly defined as a device that receives incoming signals and decodes the signals to extract information. Receiver processing is commonly utilized for multiple access communications systems such as wireless Local Area Networks, cellular land-mobile communications systems, mobile satellite communications systems, and memory storage and retrieval devices.
Within the telecommunications industry the wireless growth has been phenomenal. The proliferation of devices and the expansive content of the wireless sector equate to more and more data being transmitted. There are several known wireless systems including Code Division Multiple Access (CDMA), Frequency Division Multiple Access (FDMA) and Time Division Multiple Access (TDMA) to achieve channel access.
One of the goals of FDMA and TDMA systems is to try and prevent two potentially interfering signals from occupying the same frequency at the same time. In contrast, Code Division Multiple Access (CDMA) techniques allow signals to overlap in both time and frequency. In a CDMA system, each signal is transmitted using spread spectrum techniques wherein CDMA signals share the same frequency spectrum and in the frequency or time domain, the CDMA signals appear to overlap one another.
Despite the advancements in wireless transmission and reception, there are still problems with such wireless channels including the ability to process multiple users in a given bandwidth. For example, a base station that processes a number of cellular devices has to receive and transmit data within a certain frequency range. The ability to extract the correct data from a given user is a difficult task, especially when the effects of interference and multipaths are considered. The problem is further complicated when the number of users exceeds the number of dimensions, resulting in an overloaded condition.
As an example of one embodiment, a plurality of spread information signals, such as binary phase shift keying (BPSK) or quadrature phase shift keying (QPSK) modulation, modulate a radio frequency (RF) carrier and are jointly received as a composite signal at the receiver. Each of the spread signals overlaps all of the other spread signals, as well as noise-related signals, in both frequency and time. The receiver correlates the composite signal with one of the unique signature sequences, and the corresponding information signal is isolated and despread.
A signature sequence is normally used to represent one bit of information. Receiving the transmitted sequence or its complement indicates whether the information bit is a +1 or −1, sometimes denoted “0” or “1”. The signature sequence usually comprises N pulses, and each pulse is called a “chip”. The entire N-chip sequence, or its complement, depending on the information bit to be conveyed, is referred to as a transmitted symbol.
The receiver correlates the received signal with the complex conjugate of the known signature sequence to produce a correlation value. When a ‘large’ positive correlation results, a “0” is detected, and when a ‘large’ negative correlation results, a “1” is detected.
It should be understood that the information bits could also be coded bits, where the code is a block or convolutional code. Also, the signature sequence can be much longer than a single transmitted symbol, in which case a subsequence of the signature sequence is used to spread the information bit.
There are a host of approaches for jointly demodulating any set of interfering digitally modulated signals, including multiple digitally modulated signals. In a real world multi-user system, there are a number of independent users simultaneously transmitting signals. These transmissions have the real-time problems of multi-path and co-channel interference, fading, and dispersion that affect the received signals. As described in the art, multiple user systems communicate on the same frequency and at the same time by utilizing parameter and channel estimates that are processed by a multi-user detector. The output of the multi-user detector is an accurate estimation as to the individual bits for an individual user.
There are systems which describe multiple users that can transmit coded information on the same frequency at the same time, with the multi-user detection system separating the scrambled result into interference-free voice or data streams. Emerging receiver processing procedures allow for huge increases in the utilization of multiple access communications. The common problem is that the processing procedures in the receivers are difficult to run in real time. Advanced receiver techniques cover several areas, namely interference suppression (sometime called multi-user detection), multipath combining and space-time processing, equalization, and channel estimation. These various techniques can be mixed and matched depending upon the circumstances. Proper signal processing of transmitter and receiver yield a far greater potential than current systems.
Multi-user detection (MUD) refers to the detection of data in non-orthogonal multiplexes. MUD processing increases the number of bits available per chip or signaling dimension for systems having interference limited systems. A MUD receiver jointly demodulates co-channel interfering digital signals.
Optimal MUD based on the maximum likelihood sequence estimator operates by comparing the received signal with the entire number of possibilities that could have resulted, one for each bit or symbol epoch. Unfortunately, this processing is a computationally complex operation and it is not possible to accomplish in a real-time environment. Thus for those multi-user detectors that examine the entire space, real-time operation is often elusive.
In general, optimal MUD units function by examining a number of possibilities for each bit. However, for multi-user detectors that examine a larger capacity of signal, the computations are complex and time-consuming, thus making real-time operation impossible. Numerous attempts at reliable pruning of the optimal MUD decision process or the use of linear approximation to the replace the optimal MUD have still not produced a workable solution for the real world environment.
There are various multiuser detectors in the prior art, including optimal or maximum likelihood MUD, maximum likelihood sequence estimator for multiple interfering users, successive interference cancellation, TurboMUD or iterative MUD, and various linear algebra based multi-user detectors such as all of those detailed in the well-known text “Multiuser Detection” by Sergio Verdu. In basic terms, turbodecoding refers to breaking a large processing process into smaller pieces and performing iterative processing on the smaller pieces until the larger processing is completed. This basic principle was applied to the MUD.
There are known problems in these prior MUD designs. Linear Algebra based MUD (non-iterative) and successive interference cancellation fails for cases of overloaded multiple access systems. One example of overloading is where the number of simultaneous users is doubled relative to existing state of the art. Even for under-loaded multiple access systems, the performance of non-iterative MUD and successive interference cancellation degrades significantly as the number of users increases, while the computation complexity of the optimal MUD increases significantly as the number of users increases. More expensive and sophisticated processing is needed and there is an unreasonable processing delay required to decode each bit or symbol.
Reduced complexity approaches based on tree-pruning help to some extent to prune the proper path in the decision tree. The M-algorithm is a pruning process that limits the number of hypotheses extended to each stage to a fixed tree width and prunes based on ranking metrics for all hypotheses and retaining only the M most likely hypotheses. The T-algorithm prunes hypotheses by comparing the metrics representing all active hypotheses to a threshold based on the metric corresponding to the most-likely candidate. Performance of M-algorithm based MUD degrades as the parameter M is decreased, but M governs the number of computations required. Similar effects are seen for other tree-pruning based MUD, such as the T-algorithm. To combat improper pruning, basic tree-pruning must ensure that M is “large enough”, and therefore still encounters increased complexity for acceptable performance levels when the number of interfering signals and/or ISI lengths are moderate to large.
As an illustration of the M-algorithm as a tree-pruning algorithm, consider a tree made up of nodes and branches. Each branch has a weight or metric, and a complete path is a sequence of nodes connected by branches between the root of the tree and its branches. When applied as a short cut to the optimal MUD, each branch weight is a function of the signature signal of a certain transmitter, the possible bit or symbol value associated with that transmitter at that point in time, and the actual received signal which includes all the signals from all the interfering transmissions. The weight of each path is the sum of the branch metrics in a complete path. The goal of a tree searching algorithm is to try to find the complete path through a tree with the lowest metric. With the present invention the metrics of multiple complete paths are not calculated. Rather, the metrics of individual branches in a tree are calculated in the process of locating one complete path through the tree and thereby defines one unknown characteristic of each of the co-channel, interfering signals needed to decode the signals.
A MUD algorithm within the TurboMUD system determines discrete estimates of the transmitted channel symbols, with the estimates then provided to a bank of single-user decoders (one decoder for each user) to recover the input bit streams of all transmitted signals.
Two general types of multi-user detectors within the TurboMUD system are possible, namely those that provide hard outputs, which are discrete values, and those that provide soft outputs, which indicate both the discrete estimate and the probability that the estimate is correct.
However, single-user decoders operating on hard values, or discrete integers, have unacceptable error rates when there is a large amount of interference. The reason is that discrete integers do not provide adequate confidence values on which the single-user decoder can operate. These decoders operate better on so-called soft inputs in which confidence values can range from −1 to 1, such as for instance 0.75 as opposed to being either −1 or +1.
In an attempt to provide soft values that can then be utilized by a single-user decoder, the multi-user detector can generate these soft values. However the processing takes an inordinate amount of time. As a result, these systems do not produce real-time results. Since single-user decoders operate best on soft values, it is often times the case that the computational complexity for a robust MUD capable of generating these soft values makes it impossible to get a real-time result.
In an attempt to provide real-time performance by reducing the computational complexity of an iterative multi-user detector that can produce soft values, certain algorithms have been described for examining less than the total number of possibilities for each of the bits of data that are coming in from the multiple users. The “shortcuts” taken by this reduced complexity approach causes some errors, and combating these errors by increasing the number of iterations of the system tends to nullify any advantage.
Thus, while the MUD unit can generate soft values within the iterative cycle of the TurboMUD, the entire detection system is slowed down in generating these soft values. It should be appreciated that these soft values, rather than being integers which would be considered to be hard values, are real numbers, which in effect, permit a single user decoder to better error correct the output of the multi-user detector and thereby provide a more robust bit stream that will faithfully represent the original input for a given user.
Moreover, when dealing with hand-held communications units such as wireless handsets, the amount of processing within the device is limited, directly limiting the amount of computational complexity that is allowed. In order to provide real-time performance both at a cell site and the handset, it therefore becomes important to be able to reduce the amount of computational complexity and processing time so as to achieve real-time performance.
Existing approaches fail to address all of the aforementioned problems. What is needed is an efficient signal processing technique to improve the quality and spectral efficiency of wireless communications and better techniques for sharing the limited bandwidth among different high capacity users. As can be seen, attempts to make real-time processing multi-user processing have been frustrated by complex and sophisticated hardware and processing requirements. What is needed therefore is a method and apparatus for allowing multiple users to operate in the same channel. Such a system should provide accurate cancellation of interfering signals while reducing complex processing.